The invention relates generally to the field of signal analysis, and more particularly, to detecting the frequency, amplitude and/or phase of a plurality of tones comprised within an input signal.
In many applications, it is necessary or desirable to precisely locate multiple tones comprised in a signal. This need arises in many fields including telecommunications, radar, sonar, networking, measurement, and various other applications. Prior art techniques for detecting tones in a signal generally may not produce accurate results and/or may suffer from slow performance.
The discrete Fourier transform (DFT) is a popular tool for analyzing signals. However, before an input signal is transformed, it is quite often windowed with a windowing function. (It is noted that the action of capturing a finite-length sequence of samples of the input signal automatically implies a rectangular windowing.) The frequency transform F(n) of the windowed input signal will typically exhibit multiple scaled and shifted versions of transform function W. i.e., the transform of the window function. Each sinusoidal component of the input signal expresses itself as a pair of such shifted versions, one version shifted up to the frequency fj of the sinusoidal component, and the other shifted down to frequency xe2x88x92fj. The positive frequency version is referred to herein as a positive frequency image, and the negative frequency version is referred to herein as a negative frequency image. When a sinusoidal component frequency fj is small compared to the sample rate, the positive frequency image and the negative frequency image for the sinusoidal component may overlap in frequency space. Similarly, when a sinusoidal component frequency fj is close to one-half the sample rate, the positive frequency image and the negative frequency image for the sinusoidal component may overlap. Furthermore, when two sinusoidal components have frequencies that are close together, their positive images and negative images may overlap.
Prior art techniques for tone estimation quite often focus on identifying the peaks in the magnitude spectrum |F(n)|. The peaks roughly determine the frequency of the corresponding tones. However, because of the cross-interaction of the images from other tones, or the negative frequency image from the same tone, the peak of a positive frequency image may be perturbed away from a purely scaled and frequency-shifted version of the template function W. Thus, parameter estimation techniques which compute parameters for a given tone based only on transform array values (i.e. DFT values) in the vicinity of a corresponding image peak may not produce accurate results. Therefore, there exists a substantial need for a system and method which can estimate tone parameters from the transform array for a plurality of tones with increased accuracy.
The present invention comprises various embodiments of a system and a method for estimating signal parameters (e.g., one or more of frequency, amplitude and/or phase) of a plurality of tones present in an input signal. More particularly, a system and method are described for estimating parameters for each of a plurality of tones based on a frequency transform F(n) of the input signal, where the input signal may be windowed with a window function w(n) and transformed into the frequency domain.
In one embodiment, the method may include first receiving the input signal. For example, samples of the input signal may be received, where the samples include the plurality of tones.
One or more signal parameter estimates characterizing each of the plurality of tones may be determined based on the received samples. In one embodiment, the one or more signal parameter estimates characterizing each of the plurality of tones may comprise a knowledge base of the signal parameter estimates, and the method may further include storing a copy of the knowledge base, as a prior knowledge base.
Then, the method may generate a refined estimate of the one or more signal parameters of each respective tone of the plurality of tones, updating the one or more signal parameter estimates accordingly, where the refined estimates are generated in an iterative fashion. In other words, refined estimates of the parameters for each tone may be generated in an iterative fashion, where each successive iteration produces a more refined estimate of parameters for each tone. Updating the one or more signal parameter estimates with the refined estimate of the one or more signal parameters of the respective tone may include updating the knowledge base with the refined estimate of the one or more signal parameters of the tone, where, after updating the estimates for each tone, the knowledge base is comprised of the refined estimates for each tone.
In one embodiment, iteratively generating the refined estimate of the signal parameters of each of the respective tones may include: for each respective tone of the plurality of tones, generating a refined estimate of the one or more signal parameters of the respective tone, and updating the one or more signal parameter estimates (e.g., the knowledge base) with the refined estimate. The generating and updating for each respective tone may be performed one or more times to produce final one or more signal parameter estimates for each of the plurality of tones. In one embodiment, performing the generating and updating one or more times may include performing the generating and updating for each respective tone in an iterative manner until one or more of 1) the number of iterations exceeds a threshold number of iterations, and 2) the difference between values of the one or more signal parameters of the knowledge base and values of the one or more signal parameters of the prior knowledge base is less than a threshold value.
In one embodiment, generating a refined estimate of the one or more signal parameters of each respective tone may include: for each respective tone of the plurality of tones, iteratively applying a single tone estimation method to the respective tone, thereby generating a refined estimate of the one or more signal parameters of the respective tone, and updating said one or more signal parameter estimates with the refined estimate of the one or more signal parameters of the respective tone.
Finally, the method may include storing and/or outputting the final one or more signal parameter estimates for each of the plurality of tones in response to iteratively generating the refined estimates.
In one embodiment of the invention the method may estimate parameters for the plurality of tones based on a frequency transform F(n), e.g., a Fourier transform of the samples of the input signal. The input signal may be windowed with a window function w(n) and transformed into the frequency domain. In a preferred embodiment, the window function is a cosine-based window function. Each tone in the input signal may express itself in the frequency domain as an additive combination of two or more spectra, e.g., one centered at the tone frequency and the other at the negative of the tone frequency. These two spectra are referred to herein as the positive frequency image and the negative frequency image respectively. A tone in the input signal may also be affected by spectra (e.g., positive or negative images) from other tones present in the signal.
Thus, in one embodiment, the method may include generating a frequency transform of the samples, where the frequency transform includes frequency response data for the plurality of tones. In this embodiment, generating a refined estimate of the one or more signal parameters of each respective tone may include: for each respective tone of the plurality of tones, generating modified frequency response data for the respective tone which operates to remove effects of other tones of the plurality of tones from the frequency response data of the respective tone, using the one or more signal parameter estimates of each of the other tones, then applying a single tone estimation method to the modified frequency response data, thereby generating a refined estimate of the one or more signal parameters of the respective tone. The refined estimate of the one or more signal parameters of the respective tone may then be used to update the one or more signal parameter estimates of the respective tone. The generating, removing effects, and updating may be performed one or more times on each of the plurality of tones to generate final one or more signal parameter estimates for each of the plurality of tones.
In one embodiment, removing effects of other tones from the frequency response data of the potential local peak of the respective tone may include: determining two or more sample values proximate to the potential local peak, and, for each of the other tones, calculating an effect value for each of the two or more sample values using the estimated signal parameters for the tone. The respective effect values from each of the two or more sample values may then be subtracted from the respective sample values to generate a corresponding two or more modified sample values, comprising the modified frequency response data. The modified frequency response data may then be usable in applying the single tone estimation method. In one embodiment, the two or more sample values may be consecutive sample values.
Said another way, the method may transform the signal to produce frequency response data, then remove the effects of the other tones from each tone""s frequency response data to refine the parameter estimates. After each tone""s parameters have been refined, the process may be repeated, further refining the refined estimates for each tone by using the refined estimates of the other tones to more accurately remove the effects of the other tones from the frequency response data of each tone. In other words, the refined estimates generated in each iteration may be used to remove the effects of other tones from the frequency response data of each respective tone, after which a further refined estimate may be generated for the respective tone. The method may iterate until the desired degree of refinement is achieved or some other end condition is met.
In one embodiment, the frequency transform may comprise a windowed Fast Fourier Transform (FFT) with window function W(f), where f denotes frequency, where the estimated signal parameters for the tone comprise an amplitude A1, a frequency f1, and a phase xcfx861, and where calculating an effect value for each of the two or more sample values using the estimated signal parameters for the tone may comprise calculating:
dF(m)=A1exe2x88x92jxcfx861W(fm+f1)+A1exe2x88x92jxcfx861W(fmxe2x88x92f1),
for each sample m, wherein m denotes an index of the sample, and fm denotes the frequency bin of the sample, and where subtracting the respective effect value from each of the two or more sample values comprises subtracting a respective value of dF(m) from each of the two or more sample values.
The plurality of tones may be processed as described one or more times to generate final one or more signal parameter estimates for each of the plurality of tones. Thus, the signal parameters for each of the plurality of tones may be estimated iteratively, updating previous parameter estimates with the refined estimates each iteration.
In one embodiment, the single tone estimation method applied to each tone may identify a frequency location proximate to an amplitude peak in the frequency transform, where the amplitude peak corresponds to the tone. Two or more frequency bins may then be selected proximate to the identified frequency location in the frequency transform. The method preferably selects one or more frequency bins located on either side of the frequency location of the amplitude peak. In other words, the method may select one or more bins located on one side of the amplitude peak and one or more bins located on the other side of the amplitude peak.
The method may then determine a tone frequency value that minimizes a difference between two or more expressions, e.g., at least a first expression and a second expression. Stated another way, the method may select a tone frequency value that makes a plurality of expressions most nearly equal.
Each of the plurality of expressions may comprise a sum of one or more numerator terms divided by a sum of one or more denominator terms, wherein:
1) each of the plurality of expressions includes a tone frequency variable;
2) each numerator term and each denominator term corresponds to one of the frequency bins; and
3) a ratio of each numerator term and its corresponding denominator term represent a complex amplitude of the tone at a respective bin.
Thus, for example, the plurality of expressions may comprise a first expression and a second expression having the above characteristics.
In each expression, the tone frequency variable may represent a correct tone frequency value of the tone. The first expression may be approximately equivalent to the second expression when the correct tone frequency value is used for the tone frequency variable in the first and second complex expressions.
The step of determining a tone frequency value may comprise computing a plurality of differences between the first expression and the second expression for different respective tone frequency values of the tone frequency variable, and then selecting the tone frequency value that produces a smallest difference. The method may compute the plurality of differences by performing a Newton-Rhapson root finding method.
The expressions may be real expressions or complex expressions. Where the expressions are complex expressions, the method may involve minimizing a difference between an amplitude of the first complex expression and an amplitude of the second complex expression.
In a preferred embodiment, the first expression and the second expression have the form:       "LeftBracketingBar"                            ∑                      k            +            1                                k            +            M                          ⁢                  (                                                    F                ⁡                                  (                  n                  )                                            ⁢                                                W                  *                                ⁡                                  (                                                            f                      n                                        -                                          f                      i                                                        )                                                      -                                                            F                  *                                ⁡                                  (                  n                  )                                            ⁢                              W                ⁡                                  (                                                            f                      n                                        +                                          f                      i                                                        )                                                              )                                      ∑                      k            +            1                                k            +            M                          ⁢                  (                                                    "LeftBracketingBar"                                  W                  ⁡                                      (                                                                  f                        n                                            -                                              f                        i                                                              )                                                  "RightBracketingBar"                            2                        -                                          "LeftBracketingBar"                                  W                  ⁡                                      (                                                                  f                        n                                            +                                              f                        i                                                              )                                                  "RightBracketingBar"                            2                                )                      "RightBracketingBar"    =      "LeftBracketingBar"                            ∑                      k            +            1                                k            +            M            -            1                          ⁢                  (                                                    F                ⁡                                  (                  n                  )                                            ⁢                                                W                  *                                ⁡                                  (                                                            f                      n                                        -                                          f                      i                                                        )                                                      -                                                            F                  *                                ⁡                                  (                  n                  )                                            ⁢                              W                ⁡                                  (                                                            f                      n                                        +                                          f                      i                                                        )                                                              )                                      ∑                      k            +            1                                k            +            M            -            1                          ⁢                  (                                                    "LeftBracketingBar"                                  W                  ⁡                                      (                                                                  f                        n                                            -                                              f                        i                                                              )                                                  "RightBracketingBar"                            2                        -                                          "LeftBracketingBar"                                  W                  ⁡                                      (                                                                  f                        n                                            +                                              f                        i                                                              )                                                  "RightBracketingBar"                            2                                )                      "RightBracketingBar"  
wherein:
F(n) is the nth value of the single sided scaled FFT spectrum; and
W represents a window function, wherein the window function is shifted by a value of the tone frequency variable fi.
When the frequency transform of the samples comprises generating a power spectrum of the samples, the first expression and the second expression have the form:       "LeftBracketingBar"                            ∑                      k            +            1                                k            +            M                          ⁢                  (                                    "LeftBracketingBar"                              F                ⁡                                  (                  n                  )                                            "RightBracketingBar"                        xc3x97                          "LeftBracketingBar"                              W                ⁡                                  (                                                            f                      n                                        -                                          f                      i                                                        )                                            "RightBracketingBar"                                )                                      ∑                      k            +            1                                k            +            M                          ⁢                              "LeftBracketingBar"                          W              ⁡                              (                                                      f                    n                                    -                                      f                    i                                                  )                                      "RightBracketingBar"                    2                      "RightBracketingBar"    =      "LeftBracketingBar"                            ∑                      k            +            1                                k            +            M            -            1                          ⁢                  (                                    "LeftBracketingBar"                              F                ⁡                                  (                  n                  )                                            "RightBracketingBar"                        xc3x97                          "LeftBracketingBar"                              W                ⁡                                  (                                                            f                      n                                        -                                          f                      i                                                        )                                            "RightBracketingBar"                                )                                      ∑                      k            +            1                                k            +            M            -            1                          ⁢                              "LeftBracketingBar"                          W              ⁡                              (                                                      f                    n                                    -                                      f                    i                                                  )                                      "RightBracketingBar"                    2                      "RightBracketingBar"  
wherein:
F(n) is the nth value of the single sided scaled FFT spectrum; and
W represents a window function, wherein the window function is shifted by a value of the tone frequency variable fi.
The determined tone frequency value may comprise an approximation of the correct frequency of the tone. In other words, the determined tone frequency value represents an approximation of the correct tone frequency value. The method described herein operates to find a more exact approximation of the frequency of the tone than prior art techniques, even in the presence of noise or interference from other tones, or the negative image of the respective tone being found.
After the tone frequency value has been determined, the method may comprise storing the determined tone frequency value in a memory, or outputting the determined tone frequency value, e.g., on a display or to other systems for further analysis or processing.
The method may also then compute one or more of the amplitude and phase of the tone using the determined tone frequency value. For example, once the fi value is known, the amplitude and phase can be computed as:             A      i        ⁢          ⅇ              j        ⁢                  xe2x80x83                ⁢                  ϕ          i                      =      C    =                            ∑                      k            +            1                                k            +            M                          ⁢                  (                                                    F                ⁡                                  (                  n                  )                                            ⁢                                                W                  *                                ⁡                                  (                                                            f                      n                                        -                                          f                      i                                                        )                                                      -                                                            F                  *                                ⁡                                  (                  n                  )                                            ⁢                              W                ⁡                                  (                                                            f                      n                                        +                                          f                      i                                                        )                                                              )                                      ∑                      k            +            1                                k            +            M                          ⁢                  (                                                    "LeftBracketingBar"                                  W                  ⁡                                      (                                                                  f                        n                                            -                                              f                        i                                                              )                                                  "RightBracketingBar"                            2                        -                                          "LeftBracketingBar"                                  W                  ⁡                                      (                                                                  f                        n                                            +                                              f                        i                                                              )                                                  "RightBracketingBar"                            2                                )                    
When the frequency transform of the samples comprises generating a power spectrum of the samples, the amplitude can be computed as:       A    i    =      "LeftBracketingBar"                            ∑                      k            +            1                                k            +            M                          ⁢                  (                                    "LeftBracketingBar"                              F                ⁡                                  (                  n                  )                                            "RightBracketingBar"                        xc3x97                          "LeftBracketingBar"                              W                ⁡                                  (                                                            f                      n                                        -                                          f                      i                                                        )                                            "RightBracketingBar"                                )                                      ∑                      k            +            1                                k            +            M                          ⁢                              "LeftBracketingBar"                          W              ⁡                              (                                                      f                    n                                    -                                      f                    i                                                  )                                      "RightBracketingBar"                    2                      "RightBracketingBar"  
As mentioned above, the above steps may be iteratively performed for each of the plurality of tones to determine at least one signal parameter for each of the plurality of tones in the input signal. The above method may be performed iteratively where, for each respective tone identified, the other tones"" effects may be subtracted from the input signal, and the above single tone estimation process performed on the signal. The process may then be repeated for the next tone, and so on, generating refined estimates for the parameters of each tone.
As also described above, once all of the tones have been refined by this subtraction, the entire process may be repeated (iterated), using the refined estimates to subtract the effects of the other tones from the signal, then performing single tone estimation on the signal. Each process iteration may generate a further refined set of parameter estimations for the tones. The process iteration may be terminated upon reaching a threshold number of iterations, or when the difference between successive estimates of the tone parameters is less than a threshold value, i.e., when the desired degree of refinement has been achieved, resulting in a final set of estimates for the tone parameters. The final estimates of the tone parameters may then be stored, or output to a display or external system.
It is noted than in other embodiments, alternative single tone estimation methods may be used in place of the above single tone estimation method, such as, for example, the method described in U.S. patent application Ser. No. 09/753,164, titled xe2x80x9cSystem and Method for Estimating Tones in an Input Signalxe2x80x9d, which is incorporated by reference below.
Thus the method of the present invention operates to determine more accurate approximations of signal parameters of multiple tones present in an input signal, and operates more efficiently than prior art techniques.